1. Field
The present disclosure relates to computer systems and methods in which data resources are shared among data consumers while preserving data integrity and consistency relative to each consumer. More particularly, the disclosure concerns locking.
2. Description of the Prior Art
By way of background, although ticket locks work reasonably well for exclusive locking, they can nevertheless perform poorly at high contention levels due to the large number of CPUs spinning on the lock. On some hardware platforms, updating the lock can be slow due to the need to invalidate the corresponding cache lines on large numbers of CPUs, which degrades unlock performance.
There are a number of approaches that have been used to solve similar problems:
1. Use a combination of spinning and blocking so as to reduce memory contention on the spinlock. These schemes are well known and include exponential backoff, but have problems with unfairness, especially on large systems. More recently, this approach has been applied to ticket locking, allowing long-term spinners to sleep when running on a hypervisor.
2. Use a queued lock instead of a ticket lock. There are a large number of queued locks. However, all of these perform poorly at low levels of contention. And if software is performing and scaling well, it has to be operating at low levels of contention most of the time. Nevertheless, high levels of contention can occur from time to time, even in the Linux® kernel.
3. Use a spinlock, but calibrate delay to avoid memory contention. This can result in unfairness and delays with the lock not held, but does reduce memory contention. Such an approach has been implemented for the Linux® kernel.
4. Optimize ticket locks for more efficient spinning. As far as known, there is not a complete implementation of this idea available at present, but it multiplies the size of each lock by roughly the number of CPUs, which is prohibitive in cases such as the Linux® kernel where there can be large numbers of CPUs. The literature does mention the possibility of spinning on the stack, but this would still require some way of getting from the ticket-lock shard to the stack, which still multiplies the size by some function of the number of CPUs. It would be far better to maintain a single queue, which would provide the same memory-contention benefits at far lower memory overhead.
5. Dynamically switch between a simple spinlock and a queued lock, so that the simple spinlock is used at low contention levels and the queued lock is used at high contention levels. A few schemes are known, including:                (a) Switching between a test-and-set and queued lock.        (b) Switching between the AIX® simple lock to a NUMA-aware queued lock.        (c) Switching among multiple lock families, but using heavyweight synchronization (locking) to carry out the switch.        
However, these either exclude ticket lock, which means that they give up fairness at moderate contention levels, or have a heavyweight switch mechanism, which slows down switches and requires complex heuristics to avoid switching too often.
What is needed is a scheme that provides high performance at low levels of contention, fairness at moderate levels of contention, and avoidance of throughput collapse at high levels of contention, while avoiding heavy-weight switching mechanisms. In addition, the per-lock memory footprint should not change significantly.